package com.cet.qz.unit01.chapter1_3;

import java.util.Iterator;

/**
 * @program: algorithm
 * @description:  first->node->……->last
 * @author: 陈恩涛
 * @create: 2021-04-19 20:49
 **/
public class Steque<Item> implements Iterable<Item> {

    private class Node {
        private Item item;
        private  Node next;
    }

    private Node first;
    private Node last;

    public boolean isEmpty() {
        return first == null;
    }

    public void push(Item item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        if (last == null) {
            last = first;
        }
    }

    public Item pop() {
        if (isEmpty()) {
            throw new RuntimeException("Steque is null!");
        }
        Item result = first.item;
        first = first.next;
        if (isEmpty()) {
            last = null;
        }
        return result;
    }

    public void enqueue(Item item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        if (isEmpty()) {
            first = last;
        } else {
            oldlast.next = last;
        }
    }

    /**
     * 破坏性地连接两个同类对象的额外操作
     * @param that
     */
    public void catenation(Steque<Item> that) {
        if (isEmpty()) {
            this.first = that.first;
            this.last = that.last;
            return;
        }
        this.last.next = that.first;
        that.first = null;
        if (!that.isEmpty()) {
            this.last = that.last;
        }
        that.last = null;
    }

    @Override
    public Iterator<Item> iterator() {
        return new LinkedIterator(first);
    }

    class LinkedIterator implements Iterator<Item> {

        private Node firstNode;

        public LinkedIterator(Node firstNode) {
            this.firstNode = firstNode;
        }

        @Override
        public boolean hasNext() {
            return firstNode != null;
        }

        @Override
        public Item next() {
            Item item = firstNode.item;
            firstNode = firstNode.next;
            return item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    public static void main(String[] args) {
        Steque<Integer> steque = new Steque<>();
        steque.enqueue(1);
        steque.push(2);
        steque.enqueue(3);
        for (Integer i : steque) {
            System.out.println(i);
        }
        System.out.println("=============");

        Steque<Integer> steque1 = new Steque<>();
        steque1.enqueue(5);
        steque1.enqueue(6);
        steque1.push(7);

        steque.catenation(steque1);
        for (Integer i : steque) {
            System.out.print(i + " ");
        }
    }

}
